346. Moving Average from Data Stream
Easy

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

  • MovingAverage(int size) Initializes the object with the size of the window size.
  • double next(int val) Returns the moving average of the last size values of the stream.

 

Example 1:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

 

Constraints:

  • 1 <= size <= 1000
  • -105 <= val <= 105
  • At most 104 calls will be made to next.
Accepted
190,276
Submissions
256,781
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.28 (57 votes)

Premium

Solution


Approach 1: Array or List

Intuition

Following the description of the problem, we could simply keep track of all the incoming values with the data structure of Array or List. Then from the data structure, later we retrieve the necessary elements to calculate the average.

pic

Algorithm

  • First, we initialize a variable queue to store the values from the data stream, and the variable n for the size of the moving window.

  • At each invocation of next(val), we first append the value to the queue. We then retrieve the last n values from the queue, in order to calculate the average.

Complexity

  • Time Complexity: O(N)\mathcal{O}(N) where NN is the size of the moving window, since we need to retrieve NN elements from the queue at each invocation of next(val) function.
  • Space Complexity: O(M)\mathcal{O}(M), where MM is the length of the queue which would grow at each invocation of the next(val) function.


Approach 2: Double-ended Queue

Intuition

We could do better than the first approach in both time and space complexity.

First of all, one might notice that we do not need to keep all values from the data stream, but rather the last n values which falls into the moving window.

By definition of the moving window, at each step, we add a new element to the window, and at the same time we remove the oldest element from the window. Here, we could apply a data structure called double-ended queue (a.k.a deque) to implement the moving window, which would have the constant time complexity (O(1)\mathcal{O}(1)) to add or remove an element from both its ends. With the deque, we could reduce the space complexity down to O(N)\mathcal{O}(N) where NN is the size of the moving window.

pic

Secondly, to calculate the sum, we do not need to reiterate the elements in the moving window.

We could keep the sum of the previous moving window, then in order to obtain the sum of the new moving window, we simply add the new element and deduce the oldest element. With this measure, we then can reduce the time complexity to constant.

Algorithm

Here is the definition of the deque from Python. We have similar implementation of deque in other programming languages such as Java.

Deques are a generalization of stacks and queues (the name is pronounced deck and is short for double-ended queue). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Follow the intuition, we replace the queue with the deque and add a new variable window_sum in order to calculate the sum of moving window in constant time.

Complexity

  • Time Complexity: O(1)\mathcal{O}(1), as we explained in intuition.
  • Space Complexity: O(N)\mathcal{O}(N), where NN is the size of the moving window.


Approach 3: Circular Queue with Array

Intuition

Other than the deque data structure, one could also apply another fun data structure called circular queue, which is basically a queue with the circular shape.

pic

  • The major advantage of circular queue is that by adding a new element to a full circular queue, it automatically discards the oldest element. Unlike deque, we do not need to explicitly remove the oldest element.
  • Another advantage of circular queue is that a single index suffices to keep track of both ends of the queue, unlike deque where we have to keep a pointer for each end.

Algorithm

No need to resort to any library, one could easily implement a circular queue with a fixed-size array. The key to the implementation is the correlation between the index of head and tail elements, which we could summarize in the following formula:

tail=(head+1)modsize \text{tail} = (\text{head} + 1) \mod \text{size}

In other words, the tail element is right next to the head element. Once we move the head forward, we would overwrite the previous tail element.

pic

Complexity

  • Time Complexity: O(1)\mathcal{O}(1), as we can see that there is no loop in the next(val) function.

  • Space Complexity: O(N)\mathcal{O}(N), where NN is the size of the circular queue.


Report Article Issue

Comments: 29
acoolguy's avatar
Read More

I would mention a queue instead of a Deque here in the explanation. We aren't really using both the stack and queue aspects of this data structure. Instead we are simply using the deque as a queue.

109
Show 3 replies
Reply
Share
Report
sh0gg0th's avatar
Read More

We don't need to keep a separate count variable, len(self.queue) has a time complexity of O(1).

27
Show 2 replies
Reply
Share
Report
fliess's avatar
Read More

I think in Java solution of "Approach 2: Double-ended Queue" it would be clearer to call the result of queue.poll() as head (as per javadoc) rather than tail. Just to avoid confusion among those, who are not sure how java Deque does work internally. Minor though.

15
Show 1 reply
Reply
Share
Report
aahunt's avatar
Read More

Isn't the circular queue solution backwards regarding the head and tail? The head represents the front of the queue. When you automatically dequeue you are dequeuing the head. Enqueues occur on the tail.

public double Next(int val) {        
    _count++;
    var head = (_tail + 1) % _size;
    _windowSum = _windowSum - _queue[head] + val;
    _tail = (_tail + 1) % _size;
    _queue[_tail] = val;
    return (double)_windowSum / Math.Min(_size, _count);
}

7
Show 1 reply
Reply
Share
Report
Sithis's avatar
Read More

class MovingAverage {
    private final Queue<Integer> window;
    private final int maxSize;
    private double sum = 0.0;

    public MovingAverage(int maxSize) {
        this.window = new ArrayDeque<>(maxSize + 1);
        this.maxSize = maxSize;
    }
    
    public double next(int val) {
        window.add(val);
        sum += val;
        if (window.size() > maxSize) {
            sum -= window.poll();
        }
        return sum / window.size();
    }
}

11
Show 4 replies
Reply
Share
Report
rishabhgpt3's avatar
Read More

IMO, keeping count variable in Approach 2 can lead to integer overflow. Better to use length of self.queue

4
Reply
Share
Report
t84736's avatar
Read More

All the approaches given are broken due to integer overflow. Try having 2147483647 as part of the input. You can keep the mean instead of the sum (windowSum), or keep the sum as a double, but then you can have issues with floating point precision.

2
Show 1 reply
Reply
Share
Report
Xyzzy123's avatar
Read More

Here's a simple approach in Python. It uses a queue (specifically a deque that's limited to queue operations) to store the most-recent numbers in the sliding window. It calculates the sum(queue) / len(queue) at each pass.

This isn't quite as efficient as Approach 2, since it needs to sum the k numbers in the queue during each pass. However, I'd argue that it's shorter and easier to follow.

class MovingAverage:

    def __init__(self, size: int):
        self.size = size
        self.queue = deque()

    def next(self, val: int) -> float:
        if len(self.queue) > self.size - 1:
            self.queue.popleft()
        self.queue.append(val)
        return sum(self.queue) / len(self.queue)

Update: Here's a revised version that's more performant (next is O(1), not O(k)). It's a modification of Approach 2.

class MovingAverage:

    def __init__(self, size: int):
        self.queue = collections.deque()
        self.size = size
        self.total = 0

    def next(self, val: int) -> float:
        self.queue.appendleft(val)
        self.total += val
        if len(self.queue) > self.size:
            removed_val = self.queue.pop()
            self.total -= removed_val
        return self.total / len(self.queue)

1
Show 2 replies
Reply
Share
Report
RedHornet's avatar
Read More

another version using partial sum.

class MovingAverage {
public:
vector partialSum;
int windowSize;
int current;
/** Initialize your data structure here. */
MovingAverage(int size) {
windowSize = size;
partialSum.push_back(0);
}

double next(int val) {
    partialSum.push_back(partialSum.back() + val);
    int current = partialSum.size()-1;
    if (current <= windowSize) return partialSum.back() / current;
    else return (partialSum.back() - partialSum[current-windowSize] ) /windowSize ;
}

};

0
Reply
Share
Report
Hinduja1997's avatar
Read More

class MovingAverage {
    private Queue<Integer> queue;
    private double sum;
    private int maxSize;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        queue = new LinkedList<Integer>();
        sum = 0.0;
        maxSize = size;
    }
    
    public double next(int val) {
        if(queue.size() == maxSize){
            sum-=queue.remove();
        }
        queue.add(val);
        sum += val;
        return sum/queue.size();
    }
}

Queue with linkedlist .

0
Reply
Share
Report
Success
Details
Runtime: 32 ms, faster than 14.92% of C++ online submissions for Moving Average from Data Stream.
Memory Usage: 13.9 MB, less than 57.86% of C++ online submissions for Moving Average from Data Stream.
Next challenges:
Time Submitted
Status
Runtime
Memory
Language
06/06/2021 09:25Accepted32 ms13.9 MBcpp
05/28/2021 12:25Accepted20 ms13.9 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.